/**
 * 通过归并排序算法进行排序
 */
function merge(head1, head2) {
    let temp = {
        val: '',
        next: null
    };
    let p1 = head1, p2 = head2;
    while (p1 && p2) {
        if (p1.val <= p2.val) {
            temp.next = p1;
            p1 = p1.next;
        } else {
            temp.next = p2;
            p2 = p2.next;
        }
    }
    while (p1) {
        temp.next = p1;
        p1 = p1.next;
    }
    while (p2) {
        temp.next = p2;
        p2 = p2.next;
    }
    return temp.next;
}

function sortLink(head, last) {
    if (head === null) {
        return head;
    }
    if (head.next === last) {
        head.next = null;
        return head;
    }
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let mid = slow;
    merge(sortLink(head, mid), sortLink(mid, last));
}

function toSortLink(head) {
    sortLink(head, null);
}